package code.jzh.compiler.scanner;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

import code.jzh.compiler.util.Constants;

public class RegularExpression {
	public String regularStr;
	
	public RegularExpression() {
	}

	public RegularExpression(String regularStr) {
		this.regularStr = regularStr;
	}

	public static String formatRegularExpression(String regularStr) {
		if(regularStr==null || regularStr.length()==1)
			return regularStr;
		regularStr = expandBrackets(regularStr);
		regularStr = addCharRegularExpression(regularStr);
		regularStr = posterOrderRegularExpression(regularStr);
		return regularStr;
	}
	
	//把[0-9]扩展成 0|1|2...8|9
	public static String expandBrackets(String regularStr) {
		/*while(regularStr.contains(Constants.left_bracket+"")) {
			int openBracket = regularStr.indexOf(Constants.left_bracket);
			int closeBracket = regularStr.indexOf(Constants.right_bracket);
			String prefix = regularStr.substring(0, openBracket);
			String postfix = regularStr.substring(closeBracket+1);
			StringBuilder sb = new StringBuilder();
			for(char c=regularStr.charAt(openBracket+1); c<=regularStr.charAt(closeBracket-1); c++) {
				if(sb.length()==0)
					sb.append(Constants.left_parentheses).append(c);
				else
					sb.append(Constants.union).append(c);
			}
			sb.append(Constants.right_parentheses);
			regularStr = prefix + sb.toString() + postfix;
		}
		return regularStr;*/
		
		while(findNotEscapeChar(regularStr, Constants.left_bracket)!=-1) {
			int openBracket = findNotEscapeChar(regularStr, Constants.left_bracket);
			int closeBracket = findNotEscapeChar(regularStr, Constants.right_bracket);
			String prefix = regularStr.substring(0, openBracket);
			String postfix = regularStr.substring(closeBracket+1);
			StringBuilder sb = new StringBuilder();
			for(char c=regularStr.charAt(openBracket+1); c<=regularStr.charAt(closeBracket-1); c++) {
				String appendChar = c+"";
				if(Constants.needEscape(c)) {
					appendChar = ""+Constants.escape+c;
				}
				if(sb.length()==0)
					sb.append(Constants.left_parentheses).append(appendChar);
				else
					sb.append(Constants.union).append(appendChar);
			}
			sb.append(Constants.right_parentheses);
			regularStr = prefix + sb.toString() + postfix;
		}
		//[以后就是普通字符，不需要特殊处理，所以去掉转义符 replaceAll中 "\\\\"->"\" "\\["->"["
		regularStr = regularStr.replaceAll(""+Constants.escape+Constants.escape+Constants.escape+"[", "[");
		regularStr = regularStr.replaceAll(""+Constants.escape+Constants.escape+Constants.escape+"]", "]");
		return regularStr;
	}
	
	public static int findNotEscapeChar(String regularStr, char c) {
		int fromIndex = 0;
		int pos = regularStr.indexOf(c, fromIndex);
		while(pos!=-1) {
			if(pos>0 && regularStr.charAt(pos-1)==Constants.escape) {//转义字符\[ 不算 继续找
				fromIndex = pos+1;
			}else {
				return pos;
			}
			pos = regularStr.indexOf(c, fromIndex);
		}
		return -1;
	}
	
	//连接操作(concatenation)添加“+” 如:ab转为a+b (a)(b)转为(a)+(b)
	//假设正则的格式都是正确的
	public static String addCharRegularExpression(String regularStr) {
		if(regularStr.length()<=1)
			return regularStr;
		/*StringBuilder sb = new StringBuilder();
		for(int i=0; i<regularStr.length()-1; i++) {
			char cur = regularStr.charAt(i);
			char next = regularStr.charAt(i+1);
			sb.append(cur);
			
			if( next!=Constants.star && next!=Constants.union && next!=Constants.right_parentheses
			 && cur!=Constants.union && cur!=Constants.left_parentheses)
				sb.append(Constants.concatenation);
		}
		sb.append(regularStr.charAt(regularStr.length()-1));
		return sb.toString();*/
		
		List<String> values = new ArrayList<String>();
		List<Character> types = new ArrayList<Character>();
		for(int i=0; i<regularStr.length(); i++) {
			char cur = regularStr.charAt(i);
			if(cur==Constants.escape) {
				// \*算成一个整体 不分开 不分成\+*
				String curValue = ""+cur;
				i++;
				char next = regularStr.charAt(i);
				// 引号是个特例，只是在字符串里面出现时候需要转义 其余时候不用转义
				// \"算成两个字符 所以分成\+" NFA处理时也当成两个字符 要求输入 先\再" 所以中间加上加号"+"
				if(next==Constants.quote)
					curValue = curValue+Constants.escape+'+'+next;
				else
					curValue = curValue+next;
//				curValue += regularStr.charAt(i);
				values.add(curValue);
				types.add((char)-1);
			}else {
				values.add(cur+"");
				types.add(cur);
			}
		}
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<values.size()-1; i++) {
			String value = values.get(i);
			sb.append(value);
			char charCur = types.get(i);
			char charNext = types.get(i+1);
			if( charNext!=Constants.star && charNext!=Constants.union && charNext!=Constants.right_parentheses
				&& charCur!=Constants.union && charCur!=Constants.left_parentheses)
				sb.append(Constants.concatenation);
		}
		sb.append(values.get(values.size()-1));
		return sb.toString();
	}
	
	public static String posterOrderRegularExpression(String regularStr) {
		Stack<Character> ops = new Stack<Character>();
		Stack<String> values = new Stack<String>();
		for(int i=0; i<regularStr.length(); i++) {
			char c = regularStr.charAt(i);
			if(c==Constants.escape) {
				char next= regularStr.charAt(++i);
				values.push(c+""+next);
			}else if(!Constants.isOperator(c)) {//常规元素，非操作符
				values.push(c+"");
			}else {
				/*if(ops.isEmpty()) {
					ops.push(c);
					continue;
				}*/
				if(c==Constants.left_parentheses) {
					ops.push(c);
				}else if(c==Constants.star) {
					String value1 = values.pop();
					String newValue = value1+Constants.star;
					values.push(newValue);
				}else if(c==Constants.right_parentheses) {//右括号
					while(ops.peek()!=Constants.left_parentheses) {
						String value2 = values.pop();
						String value1 = values.pop();
						char opTop = ops.pop();
						String newValue = value1+value2+opTop;
						values.push(newValue);
					}
					ops.pop();//弹出左括号
				}else {//非右括号
//					char opTop = ops.peek();
					while( !ops.isEmpty() && ops.peek() !=Constants.left_parentheses 
						&& (Constants.precedenceEqual(ops.peek(), c) || Constants.precedenceHigher(ops.peek(), c)) ) {
						String value2 = values.pop();
						String value1 = values.pop();
						char opTop = ops.pop();
						String newValue = value1+value2+opTop;
						values.push(newValue);
					}
					ops.push(c);
				}
			}
			
		}
		
		while( !ops.isEmpty() ) {
			String value2 = values.pop();
			String value1 = values.pop();
			char opTop = ops.pop();
			String newValue = value1+value2+opTop;
			values.push(newValue);
		}
		return values.pop();
	}
	
	public static void main(String[] args) {
//		String str = "aba|b(aba|b)*ab|a|ab";
		/*String str = "\"([a-b]|!|\\\")*\"";
		str = expandBrackets(str);
		System.out.println(str);
		str = addCharRegularExpression(str);
		System.out.println(str);
		str = posterOrderRegularExpression(str);
		System.out.println(str);*/
	}
	
}
